package binarysearch.test50;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/12 13:22
 */
public class Solution1 {

    // 二分缩短时间
    public double myPow(double x, int n) {
        if (x == -1) {
            if ((n & 1) == 1) return -1;
            else return 1;
        }
        if (x == 1) {
            return 1;
        }
        if (n == Integer.MIN_VALUE) {
            return 0;
        }
        double res = 1;
        if (n > 0) {
            res = bs(x, n);
            return res;
        }
        if (n < 0) {
            n = -n;
            res = bs(x, n);
            return 1 / res;
        }
        return res;
    }

    private double bs(double x, int n) {
        if (n == 0) return 1;
        if (n == 1) return x;
        double t = bs(x, n / 2);
        if ((n & 1) == 1) {
            return t * t * x;
        } else {
            return t * t;
        }
    }
}
